import java.util.*;
/**
 * 
 * @author Tyler
 *
 */
public class AlphaBetaPlayer extends Player {
	private static class ColumnUtilityPair {
		public int column;
		public double utility;
		
		public ColumnUtilityPair(int column, double utility) {
			this.column = column;
			this.utility = utility;
		}
		
		public String toString() {
			return "(" + column + "," + utility + ")";
		}
	}
	
	private int maxDepth;

	public AlphaBetaPlayer(int maxDepth) {
		this.maxDepth = maxDepth;
	}

	public int getMove(ConnectFourBoard board) throws InterruptedException {
		return getMove(board, true, 0, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY).column;
	}
	
	private ColumnUtilityPair getMove(ConnectFourBoard board, boolean maximize, int depth, double alpha, double beta) throws InterruptedException {
		if (Thread.currentThread().isInterrupted())
			throw new InterruptedException();
		if (board.isGameOver() || depth == maxDepth)
			return new ColumnUtilityPair(-1, evaluateUtility(board));
		
		ColumnUtilityPair bestMove = new ColumnUtilityPair(-1, maximize ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY);
		List<Integer> columns = new ArrayList<>();
		for (int column = 0; column < board.getColumns(); column++) {
			columns.add(column);
		}
		Collections.shuffle(columns);
		for (int column = 0; column < board.getColumns(); column++) {
			ConnectFourBoard copy = board.clone();
			try {
				copy.placeDisc(maximize ? myDisc : myDisc.getOpponent(), columns.get(column));
				ColumnUtilityPair submove = getMove(copy, !maximize, depth + 1, alpha, beta);
				submove.column = columns.get(column);
				if (maximize) {
					if (submove.utility > bestMove.utility) {
						if (submove.utility >= beta) {
							submove.utility = Double.POSITIVE_INFINITY;
							return submove;	// Terminate early
						}
						if (submove.utility > alpha)
							alpha = submove.utility;
						bestMove = submove;
					}
				} else
					if (submove.utility < bestMove.utility) {
						if (submove.utility <= alpha) {
							submove.utility = Double.NEGATIVE_INFINITY;
							return submove;	// Terminate early
						}
						if (submove.utility < beta)
							beta = submove.utility;
						bestMove = submove;
					}
			} catch (IllegalArgumentException e) {
				continue;
			}
		}
		if (depth == 0)
			System.out.println(bestMove);
		return bestMove;
	}

	public double evaluateUtility(ConnectFourBoard board) {
		if (board.isWinner(myDisc))
			return 1;
		if (board.isWinner(myDisc.getOpponent()))
			return -1;
		return 0;
	}

	public String getName() {
		return "AlphaBeta";
	}
}